﻿#define  _CRT_SECURE_NO_WARNINGS 1

#include "List.h"

/*
将两个升序链表合并为一个新的 升序 链表并返回。
新链表是通过拼接给定的两个链表的所有节点组成的。
*/

struct ListNode
{
	int val;
	struct ListNode* next;
};

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
	if (list1 == NULL)
		return list2;
	if (list2 == NULL)
		return list1;
	struct ListNode* head = NULL, * tail = NULL;
	while (list1 != NULL && list2 != NULL)
	{
		if (list1->val < list2->val)
		{
			//尾插
			if (tail == NULL)
			{
				head = tail = list1;
			}
			else
			{
				tail->next = list1;
				tail = tail->next;
			}
			list1 = list1->next;
		}
		else
		{
			if (tail == NULL)
			{
				head = tail = list2;
			}
			else
			{
				tail->next = list2;
				tail = tail->next;
			}
			list2 = list2->next;
		}
	}
	if (list1)
		tail->next = list1;
	if (list2)
		tail->next = list2;

	return head;
}


//第二种
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
	if (list1 == NULL)
		return list2;
	if (list2 == NULL)
		return list1;
	struct ListNode* head = NULL, * tail = NULL;
	if (list1->val < list2->val)
	{
		head = tail = list1;
		list1 = list1->next;
	}
	else
	{
		head = tail = list2;
		list2 = list2->next;
	}

	while (list1 != NULL && list2 != NULL)
	{
		if (list1->val < list2->val)
		{
			//尾插
			tail->next = list1;
			list1 = list1->next;
		}
		else
		{
			tail->next = list2;
			list2 = list2->next;
		}
		tail = tail->next;

	}
	if (list1)
		tail->next = list1;
	if (list2)
		tail->next = list2;

	return head;
}

//哨兵位
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
	if (list1 == NULL)
		return list2;
	if (list2 == NULL)
		return list1;
	struct ListNode* head = NULL, * tail = NULL;
	//哨兵位
	head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));

	while (list1 != NULL && list2 != NULL)
	{
		if (list1->val < list2->val)
		{
			//尾插
			tail->next = list1;
			list1 = list1->next;
		}
		else
		{
			tail->next = list2;
			list2 = list2->next;
		}
		tail = tail->next;

	}
	if (list1)
		tail->next = list1;
	if (list2)
		tail->next = list2;

	struct ListNode* first = head->next;
	free(head);
	return first;
}